

from yacf.Frontend.Common.IRNode import *

from yacf.Frontend.C99 import c99_ast as c_ast, c99_ast

from yacf.Backends.C99.Writers.OmpWriter import OmpWriter
from yacf.Tools.Tree import getFileNode
import bisect


class IdentifierNotFound(Exception):
    def __init__(self, _id):
        self._id = _id

    def __str__(self):
        return " Identifier " + str(self._id) + " has not been declared in scope ( " + str(self._id.sequence) + " , " + str(self._id.depth) + ")"

class IncorrectIDNode(Exception):
    def __init__(self, _id):
        self._id = _id

    def __str__(self):
        return " Identifier " + str(self._id) + " has no scope information)"

class Scope(object):
    """ Scope of a declaration. 
    """
    def __init__(self, begin, end = None):
        self._begin = begin
        self._end = end

    @property
    def begin(self):
        return self._begin

    @begin.setter
    def begin(self, begin):
        self._begin = begin
    
    @property
    def end(self):
        return self._end

    @end.setter
    def end(self, end):
        self._end = end

    def __str__(self):
        return "(" + str(self._begin) + ", " + str(self._end) + ")"

    def __eq__(self, other):
        return (self._begin == other.begin) and (self._end == other.end)

    def __gt__(self, other):
        return (self._begin > other._begin)

    def __ge__(self, other):
        return (self._begin >= other._begin)

    def __lt__(self, other):
        return (self._begin < other._begin)

    def __le__(self, other):
        return (self._begin < other._begin)


class MatrixInfo(object):
    """
        Class to hold info about matrices
    """

    def __init__(self, size_x, size_y, type, lda):
        self._size_x = size_x
        self._size_y = size_y
        self._type = type # This might not be required, it is btype
        self._lda = lda

    @property
    def height(self,):
        return self._size_x;

    @property
    def width(self,):
        return self._size_y;

    @property
    def type(self,):
        return self._type;

    @property
    def lda(self,):
        return self._lda;


    def __str__(self,):
        return "Matrix " + str(self.height) + "x" \
                +  str(self.width) + " with lda " \
                + str(self.lda)





class Symbol(object):
    """    Representation of a symbol from the symbol table
 
    A symbol store the name and a pointer to the node of a declaration. 
    Also it stores its scope.

    """

    def __init__(self, name = None, node = None, type = None, 
                        scope = None, depth = None, btype = None, 
                        sizeExpression = None, extra = {}):
        self._name = name
        self._node = node
        self._type = type
        self._scope = scope
        self._depth = depth
        self._btype = btype
        self._sizeExpression = sizeExpression
	self._extra = extra

    @property
    def name(self):
        return self._name

    @name.setter
    def name(self, name):
        self._name = name

    @property
    def extra(self):
        return self._extra

    @extra.setter
    def extra(self, extra):
        self._extra = extra



    @property
    def node(self):
        return self._node

    @node.setter
    def node(self, node):
        self._node = node

    @property
    def type(self):
        return self._type

    @type.setter
    def type(self, type):
        self._type = type

    @property
    def scope(self):
        return self._scope

    @scope.setter
    def scope(self, scope):
        self._scope = scope

    @property
    def depth(self):
        return self._depth

    @depth.setter
    def depth(self, depth):
        self._depth = depth
        
    @property
    def btype(self):
        return self._btype
    
    @btype.setter
    def btype(self, btype):
        setattr(self, 'btype', btype)

    @property
    def sizeExpression(self):
        return self._sizeExpression
    
    @sizeExpression.setter
    def sizeExpression(self, expression_subtree):
        self._sizeExpression = expression_subtree #.__deepcopy__()
            
    def __str__(self):
        return "{" + self._name + ": " + str(self._btype or 'Struct') + ", " + str(self.scope) + "}"
        
    def __eq__(self, other):
        return (self._name == other.name) and (self.scope == other.scope)

    def __gt__(self, other):
        return self.scope > other.scope

    def __lt__(self, other):
        return self.scope < other.scope

# TODO: Add is complex type

class ComposedSymbol(Symbol):
    def __init__(self, name = None, node = None, type = None, scope = None, depth = None, elements = None, sizeExpression = None):
        self._elements = elements
        super(ComposedSymbol, self).__init__(name, node, type, scope,depth, sizeExpression)
        
    @property
    def elements(self):
        return self._elements

    @elements.setter
    def elements(self, elements):
        self._elements = elements
    

class SymbolList(list):
        pass

class OrderedSymbolList(SymbolList):
    def orderedInsert(self, new):
        """ Ordered insertion in a list of Symbols.
            Assumes list is already ordered from smaller to highest by scope
        """
        
        bisect.insort(self, new)
        #---------------------------------------------------- if len(self) == 0:
            #-------------------------------------------------- self.append(new)
            #-------------------------------------------------------- return new
        #----------------------------------------------------------------- else:
            #-------------------------------------- for i in range(0,len(self)):
                #------------------------------------------------ elem = self[i]
                #----------------------------------- if elem.scope <= new.scope:
#------------------------------------------------------------------------------ 
                    #-------------------- self.insert(self.index(elem) + 1, new)
                    #------------------------------------------------ return new
            #------------------------------------------------------------- else:
                #------------------------------------------- self.insert(0, new)
                #---------------------------------------------------- return new



class SymbolTable([].__class__):
    """ Symbol Table of the code.

        It is a dictionary with two additional method: lookUp, to search identifiers, and addSymbol, to insert


    Each level is represented by a key in the dictionary. Declarations inside each level are stored in a list.
    Each declaration contains a SCOPE attribute, storing the begin and end sequence numbers where this declaration is valid.

    Level-Lists are not guaranteed to be ordered by scope.

    In example:

    1. int a, b;
    2. int main() {
    3.     int b;
    4.    b = a + 1;
    5. }

    +--------+--------------------------------+
    | level  | list                           |
    +========+================================+
    |   0    | [int a (1,5), int b(1,5)]      |
    +--------+--------------------------------+
    |   1    | [int main(2, 5)]               |  
    +--------+--------------------------------+
    |   2    | [int b(3,5)]                   |
    +--------+--------------------------------+

    """

    def _lookUpField(self, _id):
        """ Returns the Symbol of a Field from a complex structure """
        if isinstance(_id, c_ast.StructRef):
#            print "Looking for field: " + str(_id.field) + " which is a StructRef (name " + str(_id.name) + ")"
            declaration = self.lookUp(_id.name)
#            print "Declaration: " + str(declaration.type) + " dir: " + str(dir(declaration))
            symbols = None
            if hasattr(declaration.type.type, 'decl_symbol'):
                # This is not the true declaration, but a partial one. Let's look the correct symbol
                # print "Partial declaration"
                symbols = self.lookUp(declaration.type.type.decl_symbol).elements
            elif hasattr(declaration.type.type, 'symbols'):
#                print "Full declaration"
                symbols = declaration.elements
#            print "Symbols " + str(symbols)
            if not symbols:
                # TODO: This should be something like "Malformed type" or "Type not found"
                raise IdentifierNotFound(_id)
            # _id.field.sequence = 0
            # _id.field.depth = 0
            # print "Looking for :" + str(_id.field) + " in " + str(_id)
            return symbols.lookUp(_id.field) 
        else:
            return self.lookUp(_id)
#            print "Looking for field: " + str(_id) + " Parent: " + str(_id.parent.name)
#            elements = self.lookUp(_id.parent.name).elements
#            return elements.lookUp(_id)


    def lookUpDecl(self, _decl):
        """ Return the symbol element from a given Decl node """
        try:
                for symbol in self[_decl.depth]:
                    if symbol.name == _decl.name and symbol.scope.begin == _decl.sequence:
                        return symbol
#                    elif symbol.name == _decl.name:
#                        print "Symbol " + symbol.name + " Ok but sequence " + str(_decl.sequence) + " is not " + str(symbol.scope.begin)
                raise IdentifierNotFound('Declaration is not in Symbol Table');
        except IndexError:
            raise IdentifierNotFound("Looking for  " + str(_decl.name) + " within an unexistant depth ")
 
    def lookUpTypeDecl(self, _typedecl):
        """ Return the symbol element from a given TypeDecl node (this comes from a typedef OR a struct) """
        try:
                act_depth = _typedecl.depth
                while act_depth >= 0:
                        for symbol in self[act_depth]:
                            if hasattr(_typedecl.type, "names"):
                                if symbol.name == _typedecl.type.names[0] and symbol.scope.begin <= _typedecl.sequence:
                                    return symbol
                            elif hasattr(_typedecl.type, "name"):
                                if symbol.name == _typedecl.type.name and symbol.scope.begin <= _typedecl.sequence:
                                    return symbol
                            else:
                                raise IdentifierNotFound('Type Declaration is not in Symbol Table');
                        act_depth -= 1
                raise IdentifierNotFound('Type Declaration is not in Symbol Table');
        except IndexError:
            raise IdentifierNotFound("Looking for  " + str(_typedecl) + " within an unexistant depth ")

    def lookUpDecl(self, _decl):
        """ Return the symbol element from a given Decl node """
        try:
                for symbol in self[_decl.depth]:
                    if symbol.name == _decl.name and symbol.scope.begin == _decl.sequence:
                        return symbol
#                    elif symbol.name == _decl.name:
#                        print "Symbol " + symbol.name + " Ok but sequence " + str(_decl.sequence) + " is not " + str(symbol.scope.begin)
                raise IdentifierNotFound('Declaration is not in Symbol Table');
        except IndexError:
            raise IdentifierNotFound("Looking for  " + str(_decl.name) + " within an unexistant depth ")

    
    @staticmethod
    def fillDeclList(sequence, symbol_list):
        tmp = []
        for symbol in symbol_list:
             if symbol.scope.begin <= sequence:
                if symbol.scope.end is None or symbol.scope.end >= sequence:
                    tmp.append(symbol)
             elif symbol.scope.begin > sequence:
                # If start is after sequence, no need to keep looking
                break

        return tmp
#        for symbol in symbol_list:
#            if symbol.scope.begin <= sequence:
#                if symbol.scope.end is None or symbol.scope.end >= sequence:
#                    decl_list.append(symbol)
#            if symbol.scope.begin <= sequence and  symbol.scope.end >= sequence:
#                decl_list.append(symbol)
#            elif symbol.scope.end is None and symbol.scope.begin <= sequence:
#                decl_list.append(symbol)


    def lookUp(self, _id):
        """ Returns the Symbol Declaration for a given ID node

        :param _id: ID node (with scope and depth info)
        :return Symbol:
        """
        if hasattr(_id, 'field'):
            return self._lookUpField(_id)
        # It is an array ref, lets look for the array name to get the symbol
        if hasattr(_id, 'array_name'):
            return self.lookUp(_id.array_name)
        try:
            if not (hasattr(_id, 'depth') and hasattr(_id, 'sequence')):
                raise IncorrectIDNode("%s has no scope attributes \n"%(_id.name));
            act_depth = min(_id.depth,len(self))
            while act_depth >= 0:
                decl_list = None
                try:
                    decl_list = SymbolTable.fillDeclList(_id.sequence, self[act_depth])
                except IndexError:
                    decl_list = None
                if decl_list:
                    for elem in decl_list:
                         if elem.node.name == _id.name:
                              return elem
                    act_depth = act_depth - 1
                else:
                    act_depth = act_depth - 1
            raise IdentifierNotFound(_id)    
        except IndexError:
            raise IdentifierNotFound(_id)

    def lookUpName(self, lexeme):
        # Create a node
        import re
        node = c_ast.ID(lexeme,sequence=0,depth=10000)
        dictLexemes = {}
        for i in range(10000):
            node.sequence = i
            try:
                lxm = self.lookUp(node)
                lxm = str(lxm)
                key = re.search(r'\(.*\)', lxm)
                dictLexemes[str(key.group(0))] = lxm
            except:
                pass
        return dictLexemes



    def buildSizeExpressionSubtree(self, node, btype, numElems):
        """ Builds the expression computing the size in bytes for a particular variable.
        
        """
        sizeExpr_subtree = c_ast.Constant(value = "1", type = "integer")
        if (type(btype) == ComposedSymbol):
            # TODO: This is enough robust?
            btype = str("struct " + btype.node.name)
        if isinstance(node, c_ast.Struct):
            # Size of structure is the sizeof(node)
            sizeExpr_subtree = c_ast.UnaryOp(op = 'sizeof', expr = node)   
        elif not isinstance(node.type, c_ast.TypeDecl):
            sizeof_ast = c_ast.UnaryOp(op = 'sizeof', expr = None)   
            sizeof_ast.expr = c_ast.Constant(value = btype, type = 'string')
            sizeExpr_subtree = c_ast.BinaryOp(op = '*', left = numElems, right = sizeof_ast) 
        elif isinstance(node.type, c_ast.TypeDecl):
            sizeof_ast = c_ast.UnaryOp(op = 'sizeof', expr = None)   
            sizeof_ast.expr = c_ast.Constant(value = btype, type = 'string')
            sizeExpr_subtree = c_ast.BinaryOp(op = '*', left = numElems, right = sizeof_ast) 
        elif isinstance(node.type, c_ast.PtrDecl) and numElems > 1:
            # This is a pointer but the size has been defined at some point
            sizeof_ast = c_ast.UnaryOp(op = 'sizeof', expr = None)   
            sizeof_ast.expr = c_ast.Constant(value = btype, type = 'string')
            sizeExpr_subtree = c_ast.BinaryOp(op = '*', left = numElems, right = sizeof_ast) 
        else:
            print "Warning: Unespecified type, assuming one "

        return sizeExpr_subtree

#
    def addSymbol(self, node, depth, sequence, btype, numElems = 0):
        """ Add a new Symbol node to the Symbol table.

            :param node: Common.IRNode of the declaration
            :param depth: Scope depth of the declaration
            :param sequence: Number of sequence of the statement in the AST
        """
        new = None
        # Do not add empty declarations to the TS
        if node.name is None:
            return        

        sizeExpression_subtree = self.buildSizeExpressionSubtree(node, btype, numElems)
        if hasattr(node, 'elements'):
            new = ComposedSymbol(name = node.name, node = node, scope = Scope(begin = sequence, end = None), \
                                depth = depth, type  = node, elements = node.elements, sizeExpression = sizeExpression_subtree)
        else:
            new = Symbol(name = node.name, node = node, scope = Scope(begin = sequence), 
                         depth = depth, type  = node.type, btype = btype, sizeExpression = sizeExpression_subtree )

        try:
                for elem in self[depth]:
                    if elem == new:
                        break
                else:
                    if len(self) > depth:
                        self[depth].orderedInsert(new)
        except IndexError:
            for i in range(len(self), depth + 1):
                self.append(OrderedSymbolList())
            self[depth].orderedInsert(new)
        except AttributeError:
            print "WTF? Incorrect elemen in TS !"
            import pdb
            pdb.set_trace()

    def __str__(self):
        buf = "\n"
        buf += " Symbol table \n"
        buf += "========================== \n"
        for olist in self:
            buf += " Level : " + str(self.index(olist)) + "\n"
            buf += "\t \n"
            buf += "["
            for elem in olist:
                if hasattr(elem, 'elements'):
                    buf += str(elem) + " --> " + str(elem.elements) + " <-- "
                else:
                    buf += str(elem)
            # buf += str([str(elem) for elem in self[key]])
            buf += "]"
            buf += "\n"
        return buf


class SymbolTableBuilder(IRNodeVisitor):
    """ Visit an AST building or updating the symbol table

    Whenever it visit an Common.IRNode that represents a new scope, the depth level
        is increased. When the childrens of the node have been visited, the
        depth is lowered again. 

    If the node is an ID, the attributes "depth" and "sequence" are inserted to
        track the identifier position in the AST
    """

    def __init__(self, symbol_table):
        self.depth = 0
        self.sequence = 0;
        self._symbol_table = symbol_table
        self._numelems = None;
        self._add_basic_types()
        # print str(self._symbol_table)
        super(SymbolTableBuilder, self).__init__()

    def _add_basic_types(self,):
        for name in ['float', 'int', 'char', 'double', 'FILE', 'bool', '__builtin_va_list', 'long']:
            subnode = c_ast.IdentifierType(names = [name,], coord = None, parent = None, sequence = 0)
            node = c_ast.TypeDecl(declname = name, quals = [], type = subnode, coord = None, parent = None, sequence = 0)
            typedef_node = c_ast.Typedef(name = name, quals = [], storage = [], type = node, coord = None, parent = None, sequence = 0)
            setattr(subnode, 'parent', node)
            setattr(node, 'parent', typedef_node)
            self._symbol_table.addSymbol(typedef_node, 0, 0, btype = subnode, numElems = self._numelems)

    def update_scope_end(self, last_position, scope_end):
        """ Update the end of the scope of current level declarations
               :param last_position: End sequence position of the previous level
               :param scope_end: End of the scope
        """
        if len(self._symbol_table) > self.depth:
            for elem in self._symbol_table[self.depth]:
                if elem.scope.begin >= last_position:
                    elem.scope.end = scope_end

    def scope_begin(self, node):
        """ Start a scope. 

            Increases the depth, visit the childrens and decrease it again.
            Every node that start a new scope calls this function.
            In general, the scope levels are: 
            Level 0: FileAST
            Level 1: Global_declarations
            Level 2: FuncDecl
            Level 3: ParamList & Compound
            Level 4: Pragma (if exists)
            Level 5..N: Nested Compound

            :param node: Node where the scope start
        """
        # Increase depth
        self.depth = self.depth + 1
        # Store the previous end of the ST
        last_position = self.sequence
        # Recursive child visit...
        node = self.generic_visit(node)
        # Update ST scopes
        self.update_scope_end(last_position, self.sequence + 1)
        # Return depth
        self.depth = self.depth - 1

    def visit_FileAST(self, node):
        self.scope_begin(node)
        self.sequence = self.sequence + 1

    def visit_FuncDef(self, node):
        # Store the previous end of the ST
        last_position = self.sequence
        # Recursive child visit...
        self.scope_begin(node.body)
        self.scope_begin(node.param_decls)
        self.visit(node.decl)
#        self.generic_visit(node)
#        # Increase depth
#        self.depth = self.depth + 1
#        # Update ST scopes end
#        self.update_scope_end(last_position, self.sequence + 1)
#        print " Scope of " + str(node.decl.name) + " end "
#        # Return depth
#        self.depth = self.depth - 1
        self.sequence = self.sequence + 1

    def visit_ParamList(self, node):
#        self.scope_begin(node)
        self.generic_visit(node)
        self.sequence = self.sequence + 1

    def visit_Compound(self, node):
        self.scope_begin(node)
        self.sequence = self.sequence + 1

    def visit_Pragma(self, node):
        self.scope_begin(node)
        self.sequence = self.sequence + 1            

    def visit_Struct(self, node):
        # This is the struct declaration
        if node.decls: #  and len(node.decls) > 0:
            #===================================================================
            # print "Struct declaration "
            #===================================================================
            tmp_table = SymbolTable()
            for decl in node.decls:
                self.visit_Decl(decl, tmp_table = tmp_table)
            # Add the symbol to the TS
            setattr(node, 'elements', tmp_table)
            self._symbol_table.addSymbol(node, self.depth, self.sequence, btype = None )
            
        # This is a reference to a previously declared struct that must exist before 
        #  this point
        else:
            # We add the decl_symbol attribute, so we now what to look in the TS
            #===================================================================
            # print "Struct partial declaration :: " + str(node.name)
            #===================================================================
            fake_id = c_ast.ID(name = node.name, sequence = self.sequence, depth = self.depth)
            setattr(node, 'decl_symbol', fake_id) 
            try:
                self._btype = self._symbol_table.lookUp(fake_id)
            except IdentifierNotFound:
                # _btype cannot be determined (probably because it is the declaration itself)
                pass
        self.sequence = self.sequence + 1

    def visit_StructRef(self, node):
        self.generic_visit(node)
        self.sequence = self.sequence + 1

    def visit_ArrayRef(self, node):
        if isinstance(node.name, c_ast.ID):
            self.visit_ID(node.name)
            # Save the ID node as the array_name
            setattr(node, 'array_name', node.name)
            self.visit(node.subscript)
        else:
            self.generic_visit(node)
            if hasattr(node.name, 'array_name'):
                setattr(node, 'array_name', node.name)
        self.sequence = self.sequence + 1


    def visit_IdentifierType(self, node):
        self._btype = node.names[0] # For now, simple types

    def visit_ArrayDecl(self, node):
        self.generic_visit(node)
        if hasattr(self, '_numelems') and self._numelems:
            self._numelems = c_ast.BinaryOp(op = '*', left = node.dim, right = self._numelems)
        else:
            self._numelems = c_ast.BinaryOp(op = '*', left = node.dim, right = c_ast.Constant(value="1", type="integer"))
    
    def visit_Decl(self, node, tmp_table = None):
        # Inherited attribute for basic type
        self._btype = None
        self._numelems = c_ast.Constant(value = "1", type = "integer")
        decl_sequence = self.sequence
        self.generic_visit(node,)
        # This declaration is inside a ComposedType (struct in this case)
        if isinstance(node.parent, c_ast.Struct):
            if tmp_table is None:
                # This is an error: If the parent is a Struct, this must be a SymbolTable
                raise NotImplemented
            #===================================================================
            # print "Adding element (decl) to a struct"
            #===================================================================
            # Declaration is added to the "TypeDecl" node
            tmp_table.addSymbol(node, 0, 0, self._btype, numElems = self._numelems)
        else:
            # Declaration is added to the Global symbol table
            #===================================================================
            # print "Adding a decl to the global ts"
            #===================================================================
            self._symbol_table.addSymbol(node, self.depth, decl_sequence,btype = self._btype, numElems = self._numelems)
        self._btype = None
        self._numelems = c_ast.Constant(value = "1", type = "integer")
        # Global sequence number is incremented 
        self.sequence = self.sequence + 1 
    
    def visit_Typedef(self, node):
        # print " Typedef " + str(node) + " ---"  + str(dir(node)) + "  Name : " + str(node.name)
        self._btype = None
        self.visit_TypeDecl(node.type)
        self._symbol_table.addSymbol(node, self.depth, self.sequence, btype = self._btype, numElems = self._numelems)
#        import pdb
#        pdb.set_trace()

    def visit_TypeDecl(self, node):
        self.generic_visit(node)
        # Assuming that typeDecl is a btype
        self._numelems = c_ast.Constant(value = "1", type = "integer")


    def visit_ID(self, node):
        """ Decorate ID nodes with sequence and depth attributes

        """
        # ID Nodes don't have the sequence attribute. We decorate them
        setattr(node, 'sequence', self.sequence)
        setattr(node, 'depth', self.depth)
        self.sequence = self.sequence + 1

    def generic_visit(self, node,):
        """ A modified version of generic_visit which increments the sequence counter 
                with each node
        """
	if node == None:
		return 
        if isinstance(node, Symbol):
            print " Node is a symbol? " + str(node)
            import pdb
            pdb.set_trace()
        if not hasattr(node, 'sequence'):
            setattr(node, 'sequence', self.sequence)
            setattr(node, 'depth', self.depth)
        elif not node.sequence:
            node.sequence = self.sequence
            node.depth = self.depth
        for c in node.children():
            self.sequence = self.sequence + 1
            self.visit(c)



symbolTableCache = {}

def getSymbolTableFromNode(node):
    """ Returns the symbol table of a given node.
         It search the parent FileAST and returns its ST
         If no FileAST, raises NodeNotValid
    """
    rootNode = getFileNode(node)
    rootNodeId = id(rootNode)
    if symbolTableCache.has_key(rootNodeId):

         st = symbolTableCache[rootNodeId]
         #tsv = SymbolTableBuilder(symbol_table = st)
         # tsv.visit(rootNode)
         return st
    # migrator = AstToIR(Writer = OmpWriter, ast = getFileNode(node))
    st = SymbolTable()
    tsv = SymbolTableBuilder(symbol_table = st)
    tsv.visit(rootNode)

    # Transform not needed because it has been cached 
    symbolTableCache[rootNodeId] = st
    return st
 
def updateSymbolTableFromNode(node):
    """ Updates the symbol table of the IR where a particular node is .
    """
    rootNode = getFileNode(node)
    rootNodeId = id(rootNode)
    if symbolTableCache.has_key(rootNodeId):
         st = symbolTableCache[rootNodeId]
         tsv = SymbolTableBuilder(symbol_table = st)
         tsv.visit(rootNode)
         return st
    # migrator = AstToIR(Writer = OmpWriter, ast = getFileNode(node))
    st = SymbolTable()
    tsv = SymbolTableBuilder(symbol_table = st)
    tsv.visit(rootNode)

    # Transform not needed because it has been cached 
    symbolTableCache[rootNodeId] = st
    return st
   
